package vip.zhenzicheng.algorithm.demo.find;

import vip.zhenzicheng.algorithm.util.ArrayUtils;

/**
 * 二分查找变形
 *
 * @author zhenzicheng
 * @date: 2022-05-17 14:15
 */
public class BSNear {

  /**
   * 有序数组中找到最左的位置
   */
  public static class BSNearLeft {

    public static void main(String[] args) {
      int[] arr = ArrayUtils.getRandomArray(50, 100);
      if (mostLeftNoLessNumIndex(arr, 2) == test(arr, 2)) {
        System.out.println("accept!");
      } else {
        System.out.println("error");
      }
    }

    /**
     * 在某个有序数组中查找到指定值出现的最左索引位置
     */
    public static int mostLeftNoLessNumIndex(int[] arr, int num) {
      if (arr == null || arr.length == 0) {
        return -1; // 代表找不到
      }
      int L = 0;
      int R = arr.length - 1;
      int ans = -1;
      while (L <= R) {
        int mid = (L + R) / 2;
        // t 更新
        if (arr[mid] >= num) {
          R = mid - 1; // 右边界缩小
          ans = mid; // 记录当前位置
        } else {
          L = mid + 1;
        }
      }
      return ans;
    }

    public static int test(int[] arr, int num) {
      for (int i = 0; i < arr.length; i++) {
        if (arr[i] >= num) {
          return i;
        }
      }
      return -1;
    }
  }

  /**
   * 最右
   */
  public static class BSNearRight {

  }

}
